<?php
/*
剑指 Offer 12. 矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。



例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"。
A B C E
S F C S
A D E E

示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

难度：中等

https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/


*/

$board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]];
$word  = "ABCCED";
$obj   = new Code_Offer12();
var_dump($obj->main($board, $word));

class Code_Offer12
{
    /*
     *  dfs+可行性剪枝：
     *  依次遍历矩阵的每个元素坐标（i, j），对其进行深度优先遍历
     *  遍历的元素替换为'/'，以表示访问过
     *  超出矩阵边界 或者 遍历的元素与目标元素不同（确实不同或者已经访问），返回false
     */
    public function main($board, $word)
    {
        $wordArray  = str_split($word);
        $wordLength = count($wordArray);
        $rows       = count($board);
        $cols       = count($board[0]);

        for ($i = 0; $i < $rows; $i++) {
            for ($j = 0; $j < $cols; $j++) {
//                if ($this->_dfs(0, $i, $j, $board, $wordArray, $wordLength)) {
                if ($this->_dfs2($board, $word, $i, $j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    protected function _dfs2($board, $word, $i, $j, $k)
    {
        // 越界
        if ($i >= count($board) || $i < 0 || $j >= count($board[0]) || $j < 0) {
            return false;
        }
        // 不匹配
        if ($board[$i][$j] != $word[$k]) {
            return false;
        }
        // 之前已经匹配了len-1个字符，此时匹配了最后一个字符，返回true
        if ($k == strlen($word) - 1) {
            return true;
        }
        // 标记访问过的字符为#
        $board[$i][$j] = '#';

        // 上左下右 四个方向dfs，匹配下一个目标元素
        $res = $this->_dfs2($board, $word, $i, $j-1, $k+1)
            || $this->_dfs2($board, $word, $i-1, $j, $k+1)
            || $this->_dfs2($board, $word, $i, $j+1, $k+1)
            || $this->_dfs2($board, $word, $i+1, $j, $k+1);

        // 回退时还原当前矩阵元素
        $board[$i][$j] = $word[$k];

        return $res;
    }

    protected function _dfs($step, $i, $j, $board, $wordArray, $wordLength)
    {
        if ($step == $wordLength) {
            return true;
        }
        // 越界
        if (!isset($board[$i][$j])) {
            return false;
        }
        // [i,j]不匹配
        if ($board[$i][$j] != $wordArray[$step]) {
            return false;
        }
        // 访问过的变成/
        $board[$i][$j] = '/';

        // 四个方向的搜索
        $up = $this->_dfs($step + 1, $i - 1, $j, $board, $wordArray, $wordLength);
        if ($up) {
            return true;
        }

        $down = $this->_dfs($step + 1, $i + 1, $j, $board, $wordArray, $wordLength);
        if ($down) {
            return true;
        }

        $left = $this->_dfs($step + 1, $i, $j - 1, $board, $wordArray, $wordLength);
        if ($left) {
            return true;
        }

        $right = $this->_dfs($step + 1, $i, $j + 1, $board, $wordArray, $wordLength);
        if ($right) {
            return true;
        }

        return false;
    }


}